package b2datastructure.graph;

import lombok.Data;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @date 2022/3/3 9:28
 * 图的两种表示方式：邻接矩阵
 */
@Data
public class Graph {
    private Map<Integer,Vertix> vertixMap;
    private Map<String,Edge>  edgeList;
    //生成顶点
    public void buildVertix(String[] data){
        vertixMap=new LinkedHashMap<>();
        for(int i=0;i<data.length;i++){
            Vertix vertix=new Vertix();
            vertix.setId(i);
            vertix.setData(String.valueOf((char)(97+i)));
            vertix.setColor(0);
            vertixMap.put(i,vertix);
        }
    }
    //生成边
    public void buildEdge(Map<Integer, List<Integer>> index){
        edgeList=new LinkedHashMap<>();
        int[][] array=new int[index.size()][index.size()];
        for(Map.Entry<Integer,List<Integer>> entry:index.entrySet()){
           List<Integer> list=entry.getValue();
           for(int i=0;i<list.size();i++){
               array[entry.getKey()][list.get(i)]=1;
               array[list.get(i)][entry.getKey()]=1;
           }
        }
        //构建边
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array.length;j++){
                System.out.print("\t"+array[i][j]);
                if(j>i){
                    int weight=array[i][j];
                    if(weight>0){
                        Edge edge=new Edge(i,j,weight);
                        edgeList.put(edge.getUnique(),edge);
                    }
                }
            }
            System.out.println();
        }
    }
    //构造顶点的边集合
    public void buildVertixEdge(Map<Integer,Vertix> vertixMap,Map<String,Edge>  edgeList){
        for(Map.Entry<Integer,Vertix> entry:vertixMap.entrySet()){
            List<Integer> vertixIds=new ArrayList<>();
            for(int i=0;i<vertixMap.size();i++){
                if(entry.getKey().intValue()!=i){
                    if(entry.getKey().intValue()>i){
                        Edge edge=edgeList.get(i+"to"+entry.getKey().intValue());
                        if(edge!=null){
                            if(!vertixIds.contains(i)){
                                vertixIds.add(i);
                            }
                        }

                    }else{
                        Edge edge=edgeList.get(entry.getKey().intValue()+"to"+i);
                        if(edge!=null){
                            if(!vertixIds.contains(i)){
                                vertixIds.add(i);
                            }
                        }
                    }
                }
            }
            entry.getValue().setVertixIds(vertixIds);
            System.out.print(entry.getKey()+"->");
            System.out.print(vertixIds.stream().map(String::valueOf).collect(Collectors.joining(",")));
            System.out.println();
        }
    }
    //BFS广度优先搜索
    public List<Integer> getBFS(Graph graph){
        List<Integer> result=new ArrayList<>();
        Random random=new Random();
        int startId=random.nextInt(8);
        Map<Integer,Vertix> vertixMap= graph.getVertixMap();
        Vertix startVertix=vertixMap.get(startId);
        Queue<Vertix> gray=new LinkedList<>();
        startVertix.setColor(1);
        gray.offer(startVertix);
        while(!gray.isEmpty()){
            Vertix current=gray.poll();
            current.setColor(2);
            result.add(current.getId());
            List<Integer> vertixNeighbour= current.getVertixIds();
            for(int i=0;i<vertixNeighbour.size();i++){
                Vertix temp=vertixMap.get(vertixNeighbour.get(i));
                if(temp.getColor().intValue()==0){
                    temp.setColor(1);
                    gray.offer(temp);
                }
            }
        }
        return result;
    }
    //DFS深度优先搜索
    public List<Integer> getDFS(Graph graph){
        return null;
    }
    public static void main(String[] args) {
        //      a   b   c   d   e   f   g   h
        //      0   1   2   3   4   5   6   7
        //          关系矩阵
        //      0	1	1	1	1	1	0	0
        //      1	0	1	0	1	0	0	0
        //      1	1	0	1	0	1	0	0
        //       1	0	1	0	1	0	0	0
        //      1	1	0	1	0	1	0	0
        //      1	0	1	0	1	0	1	1
        //      0	0	0	0	0	1	0	1
        //      0	0	0	0	0	1	1	0
        Map<Integer, List<Integer>> index=new LinkedHashMap<>();
        List<Integer> a=new ArrayList<Integer>(){
            {
                add(1);
                add(2);
                add(3);
                add(4);
                add(5);
            }
        };
        index.put(0,a);
        List<Integer> b=new ArrayList<Integer>(){
            {
                add(2);
                add(4);
            }
        };
        index.put(1,b);
        List<Integer> c=new ArrayList<Integer>(){
            {
                add(3);
            }
        };
        index.put(2,c);
        List<Integer> d=new ArrayList<Integer>(){
            {
                add(4);
            }
        };
        index.put(3,d);
        List<Integer> e=new ArrayList<Integer>(){
            {
                add(5);
            }
        };
        index.put(4,e);
        List<Integer> f=new ArrayList<Integer>(){
            {
                add(2);
                add(6);
                add(7);
            }
        };
        index.put(5,f);
        List<Integer> g=new ArrayList<Integer>(){
            {
                add(5);
                add(7);
            }
        };
        index.put(6,g);
        List<Integer> h=new ArrayList<Integer>(){
            {
                add(5);
                add(6);
            }
        };
        index.put(7,h);
        String[] data={"a","b","c","d","e","f","g","h"};
        Graph graph=new Graph();
        graph.buildVertix(data);
        graph.buildEdge(index);
        graph.buildVertixEdge(graph.getVertixMap(),graph.getEdgeList());
        List<Integer> bfsList=graph.getBFS(graph);
        for(int i=0;i<bfsList.size();i++){
            System.out.print(graph.getVertixMap().get(bfsList.get(i)).getData());
        }
    }
}
